﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

//颜⾊分类（medium）（分治）
//class Solution {
//    void PartSort3(vector<int>& nums, int left, int right)
//    {
//        if (left >= right)
//            return;
//        int key = nums[0];
//        int prev = 0;
//        int cur = 1;
//        while (cur <= right)
//        {
//            if (nums[cur] < key)
//            {
//                prev++;
//                swap(nums[prev], nums[cur]);
//            }
//            cur++;
//        }
//        swap(nums[0], nums[prev]);
//
//        PartSort3(nums, 0, prev - 1);
//        PartSort3(nums, prev + 1, right);
//    }
//
//
//public:
//    void sortColors(vector<int>& nums) {
//        int n = nums.size() - 1;
//        PartSort3(nums, 0, n);
//    }
//};
//
//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int cur = 0;
//        int prev = -1;
//        int right = nums.size();
//
//        while (cur < right)
//        {
//            if (nums[cur] == 0) swap(nums[++prev], nums[cur++]);
//            else if (nums[cur] == 1) cur++;
//            else swap(nums[--right], nums[cur]);
//        }
//    }
//};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums[i], nums[p1]);
                ++p1;
            }
            else if (nums[i] == 0) {
                swap(nums[i], nums[p0]);
                if (p0 < p1) {
                    swap(nums[i], nums[p1]);
                }
                ++p0;
                ++p1;
            }
        }
    }
};

int main()
{
	
	return 0;
}